package _17_剑指Offer;

import _17_剑指Offer.datastrcute.TreeNode;

public class _55_剑指OfferII平衡二叉树 {

    // 自底向下计算, 减少height的函数调用次数
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode node) {
        if (node == null) return 0;

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        if (leftHeight == - 1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) return -1;
        return Math.max(leftHeight, rightHeight) + 1;
    }


    // 自顶向下查找 (存在比较多的重复计算)
  /*  public boolean isBalanced1(TreeNode root) {
        if (root == null) return true;
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced1(root.left) && isBalanced1(root.right);
    }

    public int height(TreeNode node) {
        if (node == null) return 0;
        return Math.max(height(node.left), height(node.right)) + 1;
    }*/


}
